Respectând normele de distanțare socială, cei \( \frac{k\cdot (k+1)}{2} \) cetățeni din comuna lui Dorel s-au programat la magazinul din localitate pentru a face cumpărăturile de Paște, în k zile: în prima zi k cetățeni, în a doua zi k-1 dintre cei rămași, ș.a.m.d., în ultima zi ultimul cetățean.

Cerința

Fiind date t valori ale lui k, numere naturale, aflați pentru fiecare în câte moduri poate fi făcută planificarea pe zile pentru cumpărăturile de Paște.

Date de intrare

Fișierul de intrare shop.in conține pe prima linie numărul t, iar pe a doua linie t numere naturale separate prin spații, acestea fiind valorile lui k.

Date de ieșire

Fișierul de ieșire shop.out va conține pe primele t linii, răspunsul la fiecare întrebare, modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ t ≤ 1.000
• 1 ≤ k ≤ 5.000
• pentru 95p avem k ≤ 2000

Exemple:

shop.in

2
2 4

shop.out

3
12600

Explicație

Pentru k = 2 în localitate sunt 3 cetățeni, să-i notăm A, B, D. Ei pot fi programați la magazin astfel:

• {A, B}, {D}
• {A, D}, {B}
• {B, D}, {A}